package leetcode;

import leetcode.N094BinaryTreeInorderTraversal.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yinlei
 * @date 2018/6/27
 * @since 1.0.0
 */
public class N105ConstructBinaryTreefromPreorderandInorderTraversal {
    public static void main(String[] args) {
        TreeNode node = buildTree(new int[]{3,9,20,15,7}, new int[]{9,3,15,20,7});
        display(node);
        node = buildTree(new int[]{1,2,3}, new int[]{3,2,1});
        display(node);
    }

    static void display(TreeNode node) {
        List<TreeNode> nodes = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        nodes.add(node);

        while (nodes.size() > 0) {
            List<TreeNode> temp = new ArrayList<>();

            for (TreeNode item : nodes) {
                if (item == null) {
                    result.add(null);
                    continue;
                }
                result.add(item.val);
                temp.add(item.left);
                temp.add(item.right);
            }
            nodes = temp;
        }

        System.out.println(result);
    }

    static public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) return null;

        return buildTree(preorder, inorder, 0, 0, preorder.length - 1);
    }

    private static TreeNode buildTree(int[] preorder, int[] inorder, int ps, int is, int ie) {
        int val = preorder[ps];
        TreeNode node = new TreeNode(val);

        int inOffset = is;
        while (inOffset <= ie) {
            if (inorder[inOffset] == val) {
                break;
            }
            inOffset++;
        }

        if (inOffset > is) {
            node.left = buildTree(preorder, inorder, ps + 1, is, inOffset - 1);
        }
        if (inOffset < ie) {
            node.right = buildTree(preorder, inorder, ps + 1 + (inOffset - is), inOffset + 1, ie);
        }

        return node;
    }
//        if (preorder.length < 1) return null;
//
//        Map<Integer, Integer> preMap = array2Map(preorder);
//        Map<Integer, Integer> inMap = array2Map(inorder);
//
//        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1, preMap, inMap);
//    }
//
//    private static Map<Integer,Integer> array2Map(int[] preorder) {
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < preorder.length; i++) {
//            map.put(preorder[i], i);
//        }
//        return map;
//    }
//
//    static private TreeNode buildTree(int[] preorder, int[] inorder,
//                                      int pleft, int pright,
//                                      int ileft, int iright,
//                                      Map<Integer, Integer> preMap, Map<Integer, Integer> inMap) {
//        if (pleft > pright) return null;
//        TreeNode node = new TreeNode(preorder[pleft]);
//        int iindex = inMap.get(node.val);
//        // 位置不能超过边界
//        if (iindex > iright) {
//            iindex = ileft;
//        }
//        int pindex = -1;
//        if (iindex > ileft) {
//            for (int pi = pleft + 1; pi <= pright; pi++) {
//                int temp = inMap.get(preorder[pi]);
//                if (temp >= ileft && temp < iindex) {
//                    pindex = pi;
//                } else {
//                    break;
//                }
//            }
//        }
//        if (pindex != -1) {
//            node.left = buildTree(preorder, inorder, pleft + 1, pindex, ileft, iindex - 1, preMap, inMap);
//            node.right = buildTree(preorder, inorder, pindex + 1, pright, iindex + 1, iright, preMap, inMap);
//        } else {
//            node.right = buildTree(preorder, inorder, pleft + 1, pright, iindex + 1, iright, preMap, inMap);
//        }
//        return node;
//    }
    }
//    static public TreeNode buildTree(int[] preorder, int[] inorder) {
